package org.example.method;

import org.example.graph.Edge;
import org.example.graph.Vertex;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Dijkstra_better {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");

        v1.edges = List.of(new Edge(v2,7),
                new Edge(v3,9),
                new Edge(v6,14));

        v2.edges = List.of(new Edge(v4,15));
        v3.edges = List.of(new Edge(v4,11),
                new Edge(v6,2));
        v4.edges = List.of(new Edge(v5,6));
        v5.edges = List.of();
        v6.edges = List.of(new Edge(v5,9));

        List<Vertex> graph = new ArrayList<>(List.of(v1, v2, v3, v4, v5,v6));

        dijkstra(graph, v1);
    }

    private static void dijkstra(List<Vertex> graph, Vertex source) {
        PriorityQueue<Vertex> queue = new PriorityQueue<>(Comparator.comparing(Vertex -> Vertex.dist));
        source.dist = 0;

        while (!queue.isEmpty()){
            //2.找到最短路径的点
            Vertex cur = queue.poll();
            //3.跟新附近的所有节点
            updateDist(cur,queue);
            //4.删除现在的节点
            queue.remove(cur);
            cur.visited = true;
        }

        for (Vertex vertex : graph) {
            System.out.println(vertex.getName() +" "+ vertex.dist + "路径" + vertex.path.toString());

        }
    }

    private static void updateDist(Vertex cur, PriorityQueue<Vertex> queue) {
        for (Edge edge : cur.edges) {
            int dist = cur.dist + edge.weight;
            Vertex vertex = edge.linked;
            if (!vertex.visited){
                if (dist < vertex.dist){
                    vertex.dist = dist;
                    vertex.path = new ArrayList<>(cur.path);
                    vertex.path.add(cur.getName());
                    queue.offer(vertex);//java中的优先队列要重新加入才能重新排序
                }
            }
        }
    }
}
